package 剑指offer.demo7;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;

//https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?
public class 按之字形顺序打印二叉树 {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        boolean fun = true;
        ArrayList<Integer> list = new ArrayList<>();
        queue.offer(pRoot);
        while (!queue.isEmpty()) {
            if (!fun) {
                int n = queue.size();
                for (int i = 0; i < n; i++) {
                    TreeNode cur = queue.poll();
                    list.add(cur.val);

                    if (cur.right != null) queue.offer(cur.right);
                    if (cur.left != null) queue.offer(cur.left);
                }
            } else {

                int n = queue.size();
                for (int i = 0; i < n; i++) {
                    TreeNode cur = queue.poll();
                    list.add(cur.val);
                    if (cur.left != null) queue.offer(cur.left);
                    if (cur.right != null) queue.offer(cur.right);
                }
            }

            result.add(list);
            list = new ArrayList<>();
            while (!queue.isEmpty()) {
                stack.push(queue.poll());
            }
            while (!stack.isEmpty()) {
                queue.offer(stack.pop());
            }

            fun = !fun;
        }
        return result;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
}
